﻿using System.Text;

namespace DataStructure;

//顺序表（数组）类
public class SeqList<E> : IList<E>
{
    private E[] data; //存储元素的数组
    private int N; //数组中实际存储的元素个数

    //通过指定容量开辟数组空间
    public SeqList(int capacity)
    {
        data = new E[capacity];
        N = 0;
    }

    //默认数组容量为10
    public SeqList() : this(10) { }

    //获取数组容量的属性
    public int Capacity { get { return data.Length; } }

    //获取数组元素个数的属性
    public int Count { get { return N; } }

    //判断数组是否为空的属性
    public bool IsEmpty { get { return N == 0; } }

    //添加索引器，对索引的元素进行读写，索引从0开始。
    public E this[int index]
    {
        get //获取指定位置的元素值
        {
            if (index < 0 || index >= N)
            {
                throw new IndexOutOfRangeException("非法索引");
            }

            return data[index];
        }

        set //修改指定位置的元素值
        {
            if (index < 0 || index >= N)
            {
                throw new IndexOutOfRangeException("非法索引");
            }

            data[index] = value;
        }
    }

    //获取或设置数组头部的元素值
    public E First
    {
        get { return this[0]; }

        set { this[0] = value; }
    }

    //获取或设置数组尾部的元素值
    public E Last
    {
        get { return this[N - 1]; }

        set { this[N - 1] = value; }
    }

    //在数组指定位置添加元素e
    public void Add(int index, E e)
    {
        if (index < 0 || index > N)
        {
            throw new IndexOutOfRangeException("非法索引");
        }

        if (N == data.Length)
        {
            ResetCapacity(2 * data.Length);
        }

        for (int i = N - 1; i >= index; i--)
        {
            data[i + 1] = data[i];
        }

        data[index] = e;
        N++;
    }

    //在数组尾部添加元素e
    public void AddLast(E e)
    {
        Add(N, e);
    }

    //在数组头部添加元素e
    public void AddFirst(E e)
    {
        Add(0, e);
    }

    //查询数组中元素e的位置索引
    public int IndexOf(E e)
    {
        for (int i = 0; i < N; i++)
        {
            if (data[i].Equals(e))
            {
                return i;
            }
        }

        return -1;
    }

    //查询数组是否包含元素e
    public bool Contains(E e)
    {
        for (int i = 0; i < N; i++)
        {
            if (data[i].Equals(e))
            {
                return true;
            }
        }

        return false;
    }

    //删除指定位置的元素并返回该元素
    public E RemoveAt(int index)
    {
        if (index < 0 || index >= N)
        {
            throw new IndexOutOfRangeException("非法索引");
        }

        E del = data[index];

        for (int i = index + 1; i <= N - 1; i++)
        {
            data[i - 1] = data[i];
        }

        N--;
        data[N] = default;

        if (N == data.Length / 4)
        {
            ResetCapacity(data.Length / 2);
        }

        return del;
    }

    //删除数组头部位置的元素并返回该元素
    public E RemoveFirst()
    {
        return RemoveAt(0);
    }

    //删除数组尾部位置的元素并返回该元素
    public E RemoveLast()
    {
        return RemoveAt(N - 1);
    }

    //删除指定的元素e
    public bool Remove(E e)
    {
        int index = IndexOf(e);
        if (index < 0)
        {
            return false;
        }

        RemoveAt(index);
        return true;
    }

    //清空顺序表
    public void Clear()
    {
        data = new E[10];
        N = 0;
    }

    //调整数组容量的大小
    private void ResetCapacity(int newCapacity)
    {
        E[] newData = new E[newCapacity];

        for (int i = 0; i < N; i++)
        {
            newData[i] = data[i];
        }

        data = newData;
    }

    //输出顺序表（数组）类的信息
    public override string ToString()
    {
        StringBuilder result = new StringBuilder();

        result.Append($"SqList1: count={N} capacity={data.Length}\n");
        result.Append("[");
        for (int i = 0; i < N; i++)
        {
            result.Append(data[i]);
            if (i != N - 1)
                result.Append(", ");
        }
        result.Append("]");

        return result.ToString();
    }
}

class SeqList
{
    static void Main(string[] args)
    {
        //静态
        SeqList<int> list = new SeqList<int>(20);
        for (int i = 0; i < 10; i++)
        {
            list.AddLast(i);
        }
        Console.WriteLine(list);

        list.AddFirst(66);
        Console.WriteLine(list);

        list.Add(2, 77);
        Console.WriteLine(list);

        Console.WriteLine(list.First);
        Console.WriteLine(list.Last);
        Console.WriteLine(list[1]);


        list[1] = 1000;
        Console.WriteLine(list);

        list.RemoveAt(2);
        list.RemoveFirst();
        list.RemoveLast();
        list.Remove(4);
        Console.WriteLine(list);

        //动态
        SeqList<int> list2 = new SeqList<int>();
        for (int i = 0; i < 10; i++)
        {
            list2.AddLast(i); 
            Console.WriteLine(list2);
        }

        for (int i = 0; i < 6; i++)
        {
            list.RemoveLast();
            Console.WriteLine(list);
        }

        Console.Read();
    }
}
